#include <iostream>
#include <vector>
#include <memory>

using namespace std;

class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        #if 0
        /* 暴力遍历 */
        int maxProfit = 0;
        int len = prices.size();
        int minIndex = 0;
        int temp = 0;
        for(int i = 0; i < len - 1; i++)
        {
            for(int j = i + 1; j < len; j++)
            {
                if(prices[i] < prices[j])
                {
                    temp = prices[j] - prices[i];
                    if(temp > maxProfit)
                    {
                        maxProfit = temp;
                    }
                }
            }
        }
        return maxProfit;
        #endif
        /* 复杂度o（n）*/
        int cost = prices[0];           //最低成本价
        int len = prices.size();        //数组长度
        if(len <= 1) return 0;

        int maxProfit = 0;              //最大利润
        for(int i = 1; i < len; i++)
        { 
            cost = min(cost, prices[i]);
            maxProfit = max(maxProfit, prices[i] - cost);
                      
        }
        return maxProfit;

    }
};


int main()
{
    Solution solution;

    vector<int> prices = {7, 1, 5, 3, 6, 4};
    

    int maxProfit = solution.maxProfit(prices);
    cout <<"在这次股票市场中，最大利润为" << maxProfit << endl;



    return 0;
}